Longest Prefix Match (LPM) is a problem of finding the longest prefix among a number of prefixes stored in a data base that matches a given lookup key. LPM can be used in many applications and is not limited to IP routing, but since IP routing is one of the major LPM applications, the present invention will be discussed in a context of IP routing, by way of non-limiting example, only.
A Forwarding Information Base (FIB), also known as a forwarding table, is most commonly used in network bridging, routing, and similar functions, to find the proper interface to which the input interface should send a packet to be transmitted by the router. Thus, a FIB contains a set of prefixes with corresponding output interfaces. A forwarding decision is made by finding the longest prefix matching the lookup key. The most commonly used lookup key at present is the IPv4 or IPv6 destination address of the packet.
A FIB, or other device for performing LPM, can be implemented with Random Access Memories (RAM) by using algorithms, such as M-Trie, Bitmap Tree, etc., or with fast hardware lookup mechanisms, such as Ternary Content Addressable Memories (TCAM). While advanced RAM-based FIB implementations/algorithms are scalable enough to hold millions of prefixes, they are not scalable from the lookup key width perspective, as the number of accesses to FIB memory depends on the lookup key width. In general, the wider the key, the more lookups are required.
With TCAM-based FIB or LPM implementation, the lookup time is constant. However, TCAM-based FIB is not scalable in terms of the number of prefixes. The most advanced TCAM device known today has a capacity of 40 Mbit, which can be used to hold up to 0.5M prefixes.
Accordingly, there is a long felt need for a method and apparatus for performing longest prefix match lookup that is scalable both in terms of the number of prefixes and in terms of the lookup key width.